<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 
         * 回文字串
         * 输入："abc"
         * 输出：3 
         * 解释：三个回文子串: "a", "b", "c"
         * 
         * 输入："aaa"
         * 输出：6
         * 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
         * 
         * dp[i][j]，区间i->j之间的字符串是否是回文字符串,是则为true，否则为false
         * i,j区间的字符串是否回文 依赖于i+1,j-1区间的字符串是否回文
         * 
         * 如果s[i] !== s[j]，则dp[i][j]为false
         * 如果s[i] === s[j]，
         *   i和j下标相同，则是回文串，如a，只有一个字符
         *   i和j下标相差为1，也是回文串，如aa，
         *   i和j下标相差大于1，比如cabac是否是回文，此时i和j相等都是c，就要看aba是否是回文，区间是i+1,j-1，就是看dp[i+1][j-1]是否是true即可

        */
        /* 
            时间：O(n ^ 2)
            空间：O(n ^ 2)
        */
        // 动态规划
        var countSubstrings = function(s) {
            // 初始化，必须都初始化为false
            let dp = new Array(s.length).fill(0)
            for (let i = 0; i < s.length; i++) {
                dp[i] = new Array(s.length).fill(false)
            }
            // 遍历顺序
            let result = 0
            // dp[i + 1][j - 1]在左下角，所以i应该倒序，j从i开始正序，那么dp[i+1][j-1]用到的时候就已经有值了
            for (let i = s.length - 1; i >= 0; i--) {
                for (let j = i; j < s.length; j++) {
                    if (s[i] !== s[j]) {
                        dp[i][j] = false
                    } else {
                        // 包括ij相等的情况，和ij相差为1的情况
                        if (j - i <= 1) {
                            dp[i][j] = true
                            result++
                        } else if (dp[i + 1][j - 1]) {
                            // dp[i + 1][j - 1]是true，则dp[i][j]也是true，比如说aaab中，当判断aaa子串是否是true时，i=0,j=2,此时看dp[i+1][j-1]就是看dp[1][1]是否是true，就是a是true
                            dp[i][j] = true
                            result++
                        }
                    }
                }
            }
            return result
        };
        // console.log(countSubstrings('abc'));
        // console.log(countSubstrings('aaa'));
        // console.log(countSubstrings('aaab'));
        console.log(countSubstrings('abba'));
    </script>
</body>

</html>